package com.lw.leetcode.arr.c;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

/**
 * Created with IntelliJ IDEA.
 * arr
 * c
 * 446. 等差数列划分 II - 子序列
 *
 * @author liw
 * @version 1.0
 * @date 2021/8/19 10:12
 */
public class NumberOfArithmeticSlices {

    public static void main(String[] args) {
        NumberOfArithmeticSlices test = new NumberOfArithmeticSlices();
        int[] arr = test.getArr(1000);
//        int[] arr = {2,2,3,4};
//        int[] arr = {0,2000000000,-294967296};

        long l1 = System.currentTimeMillis();

        int i = test.numberOfArithmeticSlices(arr);
        System.out.println(i);

        long l2 = System.currentTimeMillis();
        i = test.numberOfArithmeticSlices2(arr);
        System.out.println(i);

        long l3 = System.currentTimeMillis();

//        System.out.println(l2 - l1);
//        System.out.println(l3 - l2);
    }


    public int numberOfArithmeticSlices(int[] nums) {
        int length = nums.length;
        List<Map<Long, Long>> list = new ArrayList<>(length);
        for (int i = 0; i < length; i++) {
            list.add(new HashMap<>(length - i));
        }
        int sum = 0;
        for (int i = 0; i < length - 1; i++) {
            long value = nums[i];
            Map<Long, Long> aMap = list.get(i);
            for (int j = i + 1; j < length; j++) {
                Map<Long, Long> bMap = list.get(j);
                long c = nums[j] - value;
                long item = aMap.getOrDefault(c, -1L) + 1L;
                bMap.put(c, item + bMap.getOrDefault(c, -1L) + 1L);
                sum += (item);
            }
        }
        return sum;
    }


    public int numberOfArithmeticSlices2(int[] nums) {
        int n = nums.length;
        // 每个 f[i] 均为哈希表，哈希表键值对为 {d : cnt}
        // d : 子序列差值
        // cnt : 以 nums[i] 为结尾，且差值为 d 的子序列数量
        List<Map<Long, Integer>> f = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            Map<Long, Integer> cur = new HashMap<>();
            for (int j = 0; j < i; j++) {
                Long d = nums[i] * 1L - nums[j];
                Map<Long, Integer> prev = f.get(j);
                int cnt = cur.getOrDefault(d, 0);
                cnt += prev.getOrDefault(d, 0);
                cnt++;
                cur.put(d, cnt);
            }
            f.add(cur);
        }
        int ans = 0;
        for (int i = 0; i < n; i++) {
            Map<Long, Integer> cur = f.get(i);
            for (Long key : cur.keySet()) ans += cur.get(key);
        }
        int a1 = 0, an = n - 1;
        int cnt = (a1 + an) * n / 2;
        return ans - cnt;
    }

    public int[] getArr(int n) {
        int[] arr = new int[n];
        for (int i = 0; i < n; i++) {
            arr[i] = (int) ((Math.random() - 0.5) * n * 2000);
        }
        return arr;
    }

}
